Perimätiedon mukaan Tukholman perusti Birger-jaarli, joka halusi estää vihollisten pääsyn Itämereltä Mälarenin järvelle. Ensimmäiset rakennukset Tukholmassa olivatkin linnoituksia, joiden tarkoituksena oli rajoittaa liikennettä näiden vesistöjen välillä. Tukholma mainitaan historiallisissa dokumenteissa vuonna 1252 ja samoihin aikoihin se sai myös kaupunkioikeudet. Kuningas Valdemar Birgerinpoika solmi Hansaliiton kanssa kauppasopimuksen Tukholmassa. Arkeologiset kaivaukset osoittavat, että Tukholmassa oli asutusta jo 1000-luvulla. 1100-luvulla nykyisen kuninkaallisen linnan mäelle rakennettiin linnoitus. 1270-luvulla fransiskaanit perustivat luostarin nykyiselle Riddarholmenille. [1]